package com.Algorithm;

import java.util.Arrays;

/**
 * 归并排序
 *
 * @author yisl
 * @create 2019-07-01 19:16
 */
public class MergeSort {

    public static void mergeSort(int[] numbers, int left, int right) {
        int t = 1;// 每组元素个数
        int size = right - left + 1;
        while (t < size) {
            int s = t;// 本次循环每组元素个数
            t = 2 * s;
            int i = left;
            while (i + (t - 1) < size) {
                merge(numbers, i, i + (s - 1), i + (t - 1));
                i += t;
            }
            if (i + (s - 1) < right)
                merge(numbers, i, i + (s - 1), right);
        }
    }
    private static void merge(int[] data, int p, int q, int r) {
        int[] B = new int[data.length];
        int s = p;
        int t = q + 1;
        int k = p;
        while (s <= q && t <= r) {
            if (data[s] <= data[t]) {
                B[k] = data[s];
                s++;
            } else {
                B[k] = data[t];
                t++;
            }
            k++;
        }
        if (s == q + 1)
            B[k++] = data[t++];
        else
            B[k++] = data[s++];
        for (int i = p; i <= r; i++)
            data[i] = B[i];

        System.out.println(Arrays.toString(data));
    }

    public static void main(String[] args) {
        int[] a = {32,43,23,13,5};
        //mergeSort(a, 0 ,4);
        //System.out.println(Arrays.toString(a));

        //递归解法
        int[] temp = new int[a.length];
        mergeSort2(a, temp, 0, a.length-1);
        System.out.println(Arrays.toString(a));
    }

    //递归写法
    public static void mergeSort1(int[] a, int[] temp, int left, int right){
        if(left < right){
            int mid = (right-left)/2+left;
            //排序左
            mergeSort1(a,temp,left,mid);
            //排序右
            mergeSort1(a,temp,mid+1,right);
            //合并
            merge(a, temp, left, mid, right);
        }
    }
    public static void merge(int[] a, int[] temp, int left, int mid, int right){
        int l_pos = left;
        int r_pos = mid+1;
        int pos = left;
        while(l_pos<=mid&&r_pos<=right){
            if(a[l_pos]<a[r_pos]){
                temp[pos++]=a[l_pos++];
            }else{
                temp[pos++]=a[r_pos++];
            }
        }
        while (l_pos<=mid){
            temp[pos++] = a[l_pos++];
        }
        while (r_pos<=right){
            temp[pos++] = a[r_pos++];
        }
        while (left<=right){
            a[left]=temp[left];
            left++;
        }
    }

    //再写一遍
    public static void mergeSort2(int[] a, int[]temp, int left, int right){
        if(left<right){
            int mid = (right-left)/2+left;
            mergeSort2(a, temp, left, mid);
            mergeSort2(a, temp, mid+1, right);
            merge2(a,temp,left,mid,right);
        }
    }
    public static void merge2(int[] a, int[] temp, int left, int mid, int right){
        int l_pos = left;
        int r_pos = mid+1;
        int pos = left;
        while(l_pos<=mid&&r_pos<=right){
            if(a[l_pos]<a[r_pos]){
                temp[pos++] = a[l_pos++];
            }else{
                temp[pos++] = a[r_pos++];
            }
        }
        while (l_pos<=mid){
            temp[pos++] = a[l_pos++];
        }
        while (r_pos<=right){
            temp[pos++] = a[r_pos++];
        }
        while (left<=right){
            a[left]=temp[left];
            left++;
        }
    }



}
